Trójmian

Limit pamięci: 32 MB

Rozważmy trójmian podniesiony do -tej potęgi: . Interesują nas współczynniki rozwinięcia tego wielomianu:

Na przykład, .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia zestawy danych w których są liczby oraz ,
• dla każdego zestawu obliczy resztę z dzielenia przez 3 współczynnika stojącego przy w rozwinięciu wielomianu ,
• dla każdego zestawu wypisze na standardowe wyjście obliczoną resztę.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita określająca liczę zestawów danych, . Po niej następuje zestawów danych, po jednym w wierszu. W każdym zestawie danych zapisane są dwie nieujemne liczby całkowite oraz oddzielone pojedynczym odstępem, , .

Wyjście

Na standardowe wyjście należy wypisać wierszy. Wiersz -ty powinien zawierać jedną dodatnią liczbę całkowitą będąca resztą z dzielenia przez dla liczb z -tego zestawu.

Przykład

Dla danych wejściowych:

5
2 0
7 4
4 5
5 3
8 15

poprawną odpowiedzią jest:

1
2
1
0
2

Autor zadania: Krzysztof Sikora.